# 作者: 丁梦娜
# 2024年06月29日20时31分58秒
# 2121435287@qq.com
# 1、自行编写位图，实现1千个随机数（值在0-1万之间）的去重
def bit_map(num_list):
    int_bit_map = 0  # python 整型可以无穷大？
    new_list = []
    for i in num_list:
        if 1 << i & int_bit_map:  # i已经存在
            pass
        else:
            new_list.append(i)
            int_bit_map = int_bit_map | 1 << i
    return new_list


# 2、sort，sorted的各种使用，上课的代码要自己写一遍(重点，没时间的同学，必须完成这一道）
def fun2():
    print('自定义排序规则')
    word_list = "This is a test string from Andrew".split()

    def my_list_sort(s):
        return s.lower()

    print(sorted(word_list, key=my_list_sort))
    print('lambda函数的使用')
    student_tuples = [
        ('jane', 'B', 12),
        ('john', 'A', 15),
        ('dave', 'B', 10),
    ]
    print(sorted(student_tuples, key=lambda x: x[0]))
    print('自定义对象 使用lambda函数')

    class Student:

        def __init__(self, name, grade, age):
            self.name = name
            self.grade = grade
            self.age = age

        def __repr__(self):
            return repr((self.name, self.grade, self.age))  # 以 元组 形式输出

    student_objects = [
        Student('jane', 'A', 15),
        Student('john', 'B', 12),
        Student('dave', 'B', 10),
    ]
    print(sorted(student_objects, key=lambda stu: stu.age))
    print('itemgetter, attrgetter 使用')
    from operator import itemgetter, attrgetter
    print(sorted(student_tuples, key=itemgetter(2)))
    print(sorted(student_objects, key=attrgetter('age')))
    print('多级排序')
    print(sorted(student_tuples, key=itemgetter(1, 2)))
    print(sorted(student_objects, key=attrgetter('grade', 'age')))
    print('排序稳定性')
    data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
    print(sorted(data, key=itemgetter(0)))
    print('字典中混合list排序')
    mydict = {'Li': ['M', 7],
              'Zhang': ['E', 2],
              'Wang': ['P', 3],
              'Du': ['C', 2],
              'Ma': ['C', 9],
              'Zhe': ['H', 7]}
    print(sorted(mydict.items(), key=lambda x: x[1][1]))
    print('列表中是字典排序')
    game_result = [
        {"name": "Bob", "wins": 10, "losses": 3, "rating": 75.00},
        {"name": "David", "wins": 3, "losses": 5, "rating": 57.00},
        {"name": "Carol", "wins": 4, "losses": 5, "rating": 57.00},
        {"name": "Patty", "wins": 9, "losses": 3, "rating": 71.48}]
    print(sorted(game_result, key=itemgetter('rating')))


# 难度作业：
#
# 3、通过自己写的hash函数，实现圣经单词词频为前10的统计（圣经在群文件）
# 输入结果如下：
# ['the', 61861] ['and', 37403] ['of', 34040] ['to', 13121] ['in', 12007] ['that', 11405] ['he', 9375] ['shall', 9321] ['unto', 8876] ['his', 8093]
class myHash:
    def __init__(self, hash_table_size):
        '''
        :param max_size: hash_table的大小
        '''
        self.hash_table_size = hash_table_size
        self.hash_table = [None] * hash_table_size  # 每个None是字典？no

    def elf_hash(self, hash_str):
        h = 0
        g = 0
        for i in hash_str:
            h = (h << 4) + ord(i)
            g = h & 0xf0000000
            if g:
                h ^= g >> 24
            h &= ~g
        return h % self.hash_table_size

    def find_hash(self, hash_str):
        '''
        判断str在hash_table中是否存在
        :param hash_str:
        :return: 存在 返回列表下标 不存在 列表为空-1 列表不空-2
        '''
        index = self.elf_hash(hash_str)
        if self.hash_table[index] is None:
            return -1  # 列表为空
        else:
            i = 0  # hash_str 所在列表下标
            for item in self.hash_table[index]:
                if item[0] == hash_str:
                    return i
                i += 1
        return -2

def fun3():
    # 初始化一个哈希表
    my_hash_table = myHash(10000)
    # 读文件
    file = open('The_Holy_Bible.txt', mode='r', encoding='utf-8')
    text = file.readline()
    while text:
        text_list = text.split()
        for w in text_list:
            # 哈希表中是否存在
            ret = my_hash_table.find_hash(w)
            index = my_hash_table.elf_hash(w)
            if ret == -1:  # 不存在 列表空
                my_hash_table.hash_table[index] = [[w, 1]]
            elif ret == -2:  # 不存在 列表不空
                my_hash_table.hash_table[index].append([w, 1])
            else:  # 存在
                my_hash_table.hash_table[index][ret][1] += 1
        text = file.readline()
    file.close()
    # 进行词频统计
    # 遍历哈希表 建立小根堆 也可以使用sort函数 进行词频的排序 统计前10名
    sort_list=[] #排序列表
    for i in my_hash_table.hash_table:#[['hi',18],['you',13],...]
        if i is None:
            pass
        else:
            for j in i:
                if len(sort_list)<10:
                    sort_list.append(j)
                    sort_list.sort(key=lambda x: x[1], reverse=True)
                else:
                    if j[1]>sort_list[9][1]:
                        sort_list[9]=j
                        sort_list.sort(key=lambda x: x[1], reverse=True)

    print(sort_list)

# 4、有时间写下红黑树的插入
if __name__ == '__main__':
    pass

    def fun1():
        # 随机1000个随机数，值在0-1万之间
        num_list = [148, 4051, 8247, 8955, 4994, 8268, 9099, 1886, 1178, 4795, 6776, 2152, 5998, 3058, 4538, 6489, 3761,
                    4021, 3433, 9295, 5414, 2828, 239, 1764, 2940, 1630, 9731, 9264, 8130, 3375, 4783, 7752, 1039, 9839,
                    5068, 6360, 6378, 5951, 1506, 3844, 7704, 8450, 9927, 5414, 3819, 1765, 8285, 8887, 6103, 7532, 3326,
                    6647, 1652, 2241, 2224, 6417, 5518, 4131, 701, 7104, 4959, 6561, 3543, 1901, 6260, 329, 2784, 473, 2222,
                    74, 4847, 9547, 8929, 5095, 8934, 4436, 5992, 9562, 4301, 7692, 1716, 4551, 4821, 4313, 8782, 9456,
                    7866, 3963, 1097, 3900, 1024, 3145, 9883, 8276, 8736, 7881, 4822, 5019, 6307, 3171, 2730, 6140, 1715,
                    226, 2836, 6245, 4921, 8750, 4809, 2347, 6409, 7906, 8012, 4883, 5195, 4697, 7136, 751, 1394, 2114,
                    3559, 7981, 5704, 312, 6471, 7194, 9731, 3211, 1151, 3774, 5772, 7612, 7234, 6271, 2167, 8978, 2601,
                    6493, 7132, 4535, 3161, 221, 5437, 4600, 6003, 2159, 442, 9466, 9217, 8746, 7885, 461, 3878, 4117, 3238,
                    5123, 1714, 6119, 9778, 8493, 9420, 6892, 1356, 3035, 6202, 8190, 2805, 5451, 8749, 3667, 3041, 9486,
                    5965, 1307, 277, 5587, 9230, 7461, 9811, 5851, 8387, 6571, 4256, 57, 3536, 6363, 7135, 4093, 5780, 8793,
                    9170, 6515, 3389, 8809, 3613, 4684, 2321, 3177, 1183, 8790, 6857, 3406, 8895, 848, 3588, 7426, 2901,
                    4710, 2147, 3730, 3951, 5909, 5417, 5228, 2026, 3652, 1614, 3635, 5998, 9833, 7905, 3614, 6749, 2663,
                    7933, 3836, 7837, 8186, 526, 5319, 7466, 5349, 1268, 2032, 9798, 8823, 7219, 135, 515, 1517, 6529, 7503,
                    5351, 5959, 3076, 8158, 5287, 950, 4780, 6419, 9837, 7199, 5910, 4915, 3679, 9313, 6827, 1465, 6624,
                    2133, 6205, 3522, 1413, 115, 1657, 5884, 1016, 8452, 258, 7084, 1550, 162, 1846, 7387, 4891, 4018, 8231,
                    7242, 26, 3765, 7106, 9693, 9252, 1863, 9671, 9242, 3899, 6708, 9616, 3370, 1816, 8351, 5862, 4394,
                    4752, 2751, 4168, 250, 517, 4140, 740, 343, 6705, 6100, 6142, 3838, 6668, 3026, 1993, 6293, 5257, 703,
                    5280, 4919, 3742, 2564, 4511, 1956, 6443, 7158, 9034, 5543, 2929, 1384, 4635, 4052, 2938, 8144, 1589,
                    5571, 9113, 147, 1511, 7919, 8542, 8652, 7669, 9125, 5371, 8431, 3441, 3742, 9090, 273, 5324, 2498,
                    7089, 8688, 4659, 206, 6612, 3821, 1587, 2648, 5268, 385, 1377, 2550, 2279, 7422, 5616, 927, 2558, 558,
                    6985, 2150, 9340, 8895, 1140, 8819, 9395, 7693, 4503, 1513, 6814, 5431, 1927, 9705, 8296, 2079, 5272,
                    6667, 9786, 2616, 5172, 9894, 4498, 9773, 1483, 5438, 5666, 4055, 1335, 2691, 9228, 9817, 819, 8676,
                    3235, 5983, 9869, 2521, 694, 6686, 2298, 5663, 6386, 5694, 3383, 6987, 8696, 8399, 8791, 7778, 9070,
                    9106, 3227, 5218, 1982, 2867, 4285, 7722, 4594, 7180, 1207, 6269, 5028, 3077, 5710, 4669, 1987, 5170,
                    6308, 7544, 6895, 6839, 5206, 2067, 4506, 6687, 5, 9199, 8986, 4737, 6284, 4943, 3246, 7780, 7669, 369,
                    1123, 1487, 5511, 1701, 4671, 1245, 282, 527, 3309, 8211, 8736, 4520, 6380, 6814, 9623, 5429, 4511,
                    3656, 1134, 4527, 7777, 4682, 9369, 3754, 6898, 3227, 8584, 364, 1355, 6433, 2666, 5596, 3209, 6999,
                    8525, 3967, 1106, 1400, 2124, 981, 8312, 2988, 6765, 7485, 6851, 1562, 7181, 6590, 4033, 4167, 5964,
                    9914, 5986, 637, 3050, 4555, 5075, 9804, 199, 8773, 5447, 2431, 6133, 4586, 6071, 5198, 6794, 3164,
                    2699, 5657, 8035, 9313, 58, 6925, 9406, 4087, 5169, 7629, 2554, 8422, 1334, 3929, 289, 5762, 7253, 9605,
                    4604, 9082, 3098, 5062, 2702, 5416, 3206, 3454, 4343, 9101, 1158, 266, 2952, 8110, 1383, 1976, 2940,
                    9382, 3552, 9996, 5960, 3778, 5853, 4272, 5786, 4820, 9543, 3612, 4494, 7661, 9909, 2910, 6719, 9413,
                    1605, 8254, 4150, 7711, 2118, 1279, 3868, 5521, 4527, 2968, 7361, 1398, 9747, 3044, 7001, 7334, 8764,
                    9428, 6051, 8279, 6570, 9343, 9851, 5316, 9010, 8570, 5326, 9926, 8068, 431, 7833, 8606, 5136, 3578,
                    1708, 9981, 7882, 5939, 4391, 5601, 1704, 4666, 1136, 6665, 2888, 5921, 1638, 4847, 6165, 5552, 6676,
                    6508, 1896, 1607, 3445, 1347, 3675, 3792, 2437, 2077, 1339, 3371, 7365, 6348, 4118, 6456, 9290, 444,
                    881, 7946, 4804, 7646, 9179, 5936, 7308, 7493, 7086, 6582, 1768, 5690, 834, 4035, 6488, 2579, 7799,
                    3023, 3763, 8969, 9077, 9865, 939, 4540, 6565, 1324, 901, 6013, 3704, 2483, 7582, 4181, 2840, 1029,
                    5895, 4935, 7007, 9664, 3678, 5505, 1833, 7804, 7634, 2618, 9210, 3155, 7374, 5761, 689, 6498, 36, 4023,
                    3975, 4400, 6312, 1368, 4536, 5525, 2446, 1120, 3956, 7585, 6889, 3866, 1328, 9536, 5606, 9766, 7118,
                    3337, 8790, 7663, 8103, 1098, 2032, 2778, 1487, 1804, 7429, 6526, 2051, 6098, 9420, 9104, 4532, 1825,
                    5733, 9059, 8940, 8738, 3955, 422, 2524, 187, 1059, 3803, 6058, 6592, 3879, 9085, 3351, 7930, 8602,
                    3119, 5608, 9181, 281, 5495, 1093, 8746, 2942, 9329, 2491, 610, 9585, 9550, 1895, 8824, 947, 8960, 7999,
                    3238, 7858, 329, 5307, 3719, 4685, 3244, 2426, 7245, 9306, 2787, 8906, 2809, 4296, 3702, 2461, 5066,
                    4726, 7842, 891, 4192, 2129, 2930, 5923, 9777, 1293, 4472, 2367, 9146, 2710, 7998, 7638, 1839, 2991,
                    7452, 2208, 6608, 8113, 4619, 3501, 9220, 3386, 7329, 874, 7295, 6021, 3156, 6626, 4088, 8742, 6146,
                    4689, 7455, 4603, 128, 8483, 7465, 4564, 9416, 2487, 6695, 3551, 934, 9049, 904, 5923, 8440, 5147, 2969,
                    1834, 7639, 6074, 8264, 7370, 3154, 844, 3918, 7906, 93, 2771, 1853, 4514, 2941, 7344, 4529, 9769, 87,
                    2220, 2634, 6524, 3163, 1363, 2623, 2019, 5750, 5600, 7885, 1852, 4825, 7459, 9630, 3187, 7311, 3826,
                    3869, 6957, 3355, 8401, 8649, 9308, 188, 3772, 3170, 5277, 3229, 8254, 84, 319, 506, 4681, 194, 4328,
                    3220, 1946, 2352, 5920, 6915, 4109, 10000, 9125, 6927, 9710, 9139, 6824, 7569, 6351, 2107, 1629, 9056,
                    642, 5525, 340, 2357, 3711, 7326, 8704, 4465, 3245, 1373, 5326, 5865, 5281, 7780, 7694, 4077, 1057,
                    5100, 9356, 7351, 9403, 6978, 3648, 6042, 8402, 5009, 9740, 516, 7107, 6645, 9806, 6834, 2103, 9256,
                    2067, 8881, 5129, 1408, 8466, 7755, 3004, 8385, 1168, 2637, 1856, 801, 7214, 7432, 2302, 1977, 3134,
                    5008, 2160, 6050, 4245, 9679, 7587, 2273, 2898, 2066, 3684, 4912, 483, 4090, 3390, 6684, 5773, 4427,
                    3819, 6616, 3957, 4589, 6558, 8263, 4, 5064, 7982, 8999, 1015, 1429, 1562, 5071, 6648, 2961, 5438, 7251,
                    4309, 103, 1352, 4121, 6204, 7032, 4252, 6312, 6673, 1200, 5627, 3302, 1834, 4128, 9115, 8560]
        print(bit_map(num_list))
